package 我的Java学习_算法基础.day_05;

import static java.lang.Math.max;
import static java.lang.Math.min;
import static 我的Java学习_算法基础.day_05.HeightArray.getHeight;
import static 我的Java学习_算法基础.day_05._085_字符串匹配之后缀数组_中.getSa2;

public class _090_后缀数组的应用_下 {

    public static void main(String[] args) {
        int res = maxRepeatSubString("12312323");
        System.out.println(res);
    }

    private static int maxRepeatSubString(String src) {
        Suff[] sa = getSa2(src);
        int[] height = getHeight(src, sa);
        int l = 0;
        int r = height.length;
        int ans = 0;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (check(height, sa, mid)) {
                if (mid == height.length / 2)
                    return mid;
                l = mid + 1;
                ans = mid;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }

    /**
     * 用len将height分组，小于组和大于组交替
     * 在大于组中更新最大最小原始下标，大转小的时候检查上一个大于组是否满足不重叠
     * 在小于组中，只需持续更新原始下标赋值给max和min，这样小转大时候，可以保留小于组最后元素下标
     *
     * @param height
     * @param sa
     * @param len
     * @return
     */
    private static boolean check(int[] height, Suff[] sa, int len) {
        int minIndex = sa[0].index;
        int maxIndex = sa[0].index;
        for (int i = 1; i < height.length; i++) {
            int index = sa[i].index;
            if (height[i] >= len) {
                minIndex = min(minIndex, index);
                maxIndex = max(maxIndex, index);
            } else {
                if (maxIndex - minIndex >= len) {
                    return true;
                }
                maxIndex = index;
                minIndex = index;
            }
        }
        return false;
    }
}
